/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package evaluation;

import java.util.*;
import util.Pair;


/**
 * simple directed graph with labeled edges and vertices (no loop)
 * @author phong
 */
public class Graph {
    Set<Vertex> vertices;
    Set<Edge> edges;
    
    List<Vertex> marks;
    
    public Graph() {
        vertices = new LinkedHashSet<Vertex>();
        edges = new LinkedHashSet<Edge>();
        marks = new LinkedList<Vertex>();
    }
    
    public static Graph createEmptyGraph() {
        return new Graph();
    }
    
    public Graph(Set<Vertex> vs, Set<Edge> es, List<Vertex> ms) {
        this.vertices = vs;
        this.edges = es;
        this.marks = ms;
    }
    
    public Graph copy() {
        return new Graph(
                new LinkedHashSet<Vertex>(this.vertices), 
                new LinkedHashSet<Edge>(this.edges), 
                new LinkedList<Vertex>(this.marks));
    }
    
    public void addVertex(Vertex v) {
        vertices.add(v);
    } 
    
    public void addEdge(Edge e) {
        Pair<Vertex,Vertex> vs = e.getVerices();
        vertices.add(vs.getFirst());
        vertices.add(vs.getSecond());
        edges.add(e);
    }
    
    public boolean removeEdge(Edge e) {
        return this.edges.remove(e);
    }
    
    public boolean removeVertex(Vertex v) {
        boolean in = this.vertices.remove(v);
        if (in) {
            this.marks.remove(v);
            Iterator<Edge> itor = this.edges.iterator();
            while (itor.hasNext()) {
                Edge e = itor.next();
                if (e.getFirstVertex().equals(v) || e.getSecondVertex().equals(v))
                    itor.remove();
            }
            return true;
        }
        else 
            return false;
    }
    
    public void merge(Graph g) {
        this.vertices.addAll(g.vertices);
        this.edges.addAll(g.edges);
    }
    
    public void addMarks(Vertex v) {
        vertices.add(v);
        marks.add(v);
    }
    
    public Set<Vertex> getVertices() {
        return this.vertices;
    }
    
    public Set<Vertex> getVertices(int Type) {
        Set<Vertex> vs = new HashSet<Vertex>();
        for (Vertex v : this.vertices) {
            if (v.getType() == Type)
                vs.add(v);
        }
        return vs;
    }
    
    public Set<Edge> getEdges() {
        return this.edges;
    }
    
    public List<Vertex> getMarks() {
        return this.marks;
    }
    
    public Edge getEdges(Vertex v1, Vertex v2) {
        for (Edge e : this.edges) {
            if (e.getFirstVertex().equals(v1) && e.getSecondVertex().equals(v2))
                return e;
        }
        return null;
    }
    
    public List<Edge> getEdgesWFstVertex(Vertex v) {
        List<Edge> es = new LinkedList<Edge>();
        for (Edge e : this.edges) {
            if (e.getFirstVertex().equals(v))
                es.add(e);
        }
        return es;        
    }

    public List<Edge> getEdgesWSndVertex(Vertex v) {
        List<Edge> es = new LinkedList<Edge>();
        for (Edge e : this.edges) {
            if (e.getSecondVertex().equals(v))
                es.add(e);
        }
        return es;        
    }
    
    @Override
    public boolean equals(Object o) {
        if (o instanceof Graph) {
            Graph that = (Graph)o;
            return this.edges.equals(that.edges) && this.vertices.equals(that.vertices);
        }
        return false;
    }
    
    public String toDOTformat() {
        StringBuffer buff = new StringBuffer();
        buff.append("digraph G {\n");
        
        for (Edge e : this.edges) {
            buff.append(e.getFirstVertex().toString()).append(" -> ").append(e.getSecondVertex()).append(";\n");
        }
        
        buff.append("}");
        
        return buff.toString();
    }
    
    // just for test
    public void reduce(int n) {
        Iterator<Vertex> itor = this.vertices.iterator();
        int i = 0;
        while (itor.hasNext() && i < n) {
            i++;
            Vertex v = itor.next();
            System.out.println(v);
            
            itor.remove();
            this.marks.remove(v);
            Iterator<Edge> eitor = this.edges.iterator();
            while (eitor.hasNext()) {
                Edge e = eitor.next();
                if (e.getFirstVertex().equals(v) || e.getSecondVertex().equals(v))
                    eitor.remove();
            }
        }
        System.out.println("--------");
    }
}
